home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Libraries / Berkeley DB 1.6 / btree / bt_delete.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-06-04  |  9.0 KB  |  318 lines  |  [TEXT/????]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bt_delete.c    8.1 (Berkeley) 6/4/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/types.h>
  42.  
  43. #include <errno.h>
  44. #include <stdio.h>
  45. #include <string.h>
  46.  
  47. #include <db.h>
  48. #include "btree.h"
  49.  
  50. static int bt_bdelete __P((BTREE *, const DBT *));
  51.  
  52. /*
  53.  * __BT_DELETE -- Delete the item(s) referenced by a key.
  54.  *
  55.  * Parameters:
  56.  *    dbp:    pointer to access method
  57.  *    key:    key to delete
  58.  *    flags:    R_CURSOR if deleting what the cursor references
  59.  *
  60.  * Returns:
  61.  *    RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
  62.  */
  63. int
  64. __bt_delete(dbp, key, flags)
  65.     const DB *dbp;
  66.     const DBT *key;
  67.     u_int flags;
  68. {
  69.     BTREE *t;
  70.     int status;
  71.  
  72.     t = dbp->internal;
  73.     if (ISSET(t, B_RDONLY)) {
  74.         errno = EPERM;
  75.         return (RET_ERROR);
  76.     }
  77.     switch(flags) {
  78.     case 0:
  79.         status = bt_bdelete(t, key);
  80.         break;
  81.     case R_CURSOR:
  82.         /*
  83.          * If flags is R_CURSOR, delete the cursor; must already have
  84.          * started a scan and not have already deleted the record.  For
  85.          * the delete cursor bit to have been set requires that the
  86.          * scan be initialized, so no reason to check.
  87.          */
  88.         if (!ISSET(t, B_SEQINIT))
  89.                         goto einval;
  90.         status = ISSET(t, B_DELCRSR) ?
  91.             RET_SPECIAL : __bt_crsrdel(t, &t->bt_bcursor);
  92.         break;
  93.     default:
  94. einval:        errno = EINVAL;
  95.         return (RET_ERROR);
  96.     }
  97.     if (status == RET_SUCCESS)
  98.         SET(t, B_MODIFIED);
  99.     return (status);
  100. }
  101.  
  102. /*
  103.  * BT_BDELETE -- Delete all key/data pairs matching the specified key.
  104.  *
  105.  * Parameters:
  106.  *    tree:    tree
  107.  *    key:    key to delete
  108.  *
  109.  * Returns:
  110.  *    RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
  111.  */
  112. static int
  113. bt_bdelete(t, key)
  114.     BTREE *t;
  115.     const DBT *key;
  116. {
  117.     EPG *e, save;
  118.     PAGE *h;
  119.     pgno_t cpgno, pg;
  120.     indx_t cindex;
  121.     int deleted, dirty1, dirty2, exact;
  122.  
  123.     /* Find any matching record; __bt_search pins the page. */
  124.     if ((e = __bt_search(t, key, &exact)) == NULL)
  125.         return (RET_ERROR);
  126.     if (!exact) {
  127.         mpool_put(t->bt_mp, e->page, 0);
  128.         return (RET_SPECIAL);
  129.     }
  130.  
  131.     /*
  132.      * Delete forward, then delete backward, from the found key.  The
  133.      * ordering is so that the deletions don't mess up the page refs.
  134.      * The first loop deletes the key from the original page, the second
  135.      * unpins the original page.  In the first loop, dirty1 is set if
  136.      * the original page is modified, and dirty2 is set if any subsequent
  137.      * pages are modified.  In the second loop, dirty1 starts off set if
  138.      * the original page has been modified, and is set if any subsequent
  139.      * pages are modified.
  140.      *
  141.      * If find the key referenced by the cursor, don't delete it, just
  142.      * flag it for future deletion.  The cursor page number is P_INVALID
  143.      * unless the sequential scan is initialized, so no reason to check.
  144.      * A special case is when the already deleted cursor record was the
  145.      * only record found.  If so, then the delete opertion fails as no
  146.      * records were deleted.
  147.      *
  148.      * Cycle in place in the current page until the current record doesn't
  149.      * match the key or the page is empty.  If the latter, walk forward,
  150.      * skipping empty pages and repeating until a record doesn't match
  151.      * the key or the end of the tree is reached.
  152.      */
  153.     cpgno = t->bt_bcursor.pgno;
  154.     cindex = t->bt_bcursor.index;
  155.     save = *e;
  156.     dirty1 = 0;
  157.     for (h = e->page, deleted = 0;;) {
  158.         dirty2 = 0;
  159.         do {
  160.             if (h->pgno == cpgno && e->index == cindex) {
  161.                 if (!ISSET(t, B_DELCRSR)) {
  162.                     SET(t, B_DELCRSR);
  163.                     deleted = 1;
  164.                 }
  165.                 ++e->index;
  166.             } else {
  167.                 if (__bt_dleaf(t, h, e->index)) {
  168.                     if (h->pgno != save.page->pgno)
  169.                         mpool_put(t->bt_mp, h, dirty2);
  170.                     mpool_put(t->bt_mp, save.page, dirty1);
  171.                     return (RET_ERROR);
  172.                 }
  173.                 if (h->pgno == save.page->pgno)
  174.                     dirty1 = MPOOL_DIRTY;
  175.                 else
  176.                     dirty2 = MPOOL_DIRTY;
  177.                 deleted = 1;
  178.             }
  179.         } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0);
  180.  
  181.         /*
  182.          * Quit if didn't find a match, no next page, or first key on
  183.          * the next page doesn't match.  Don't unpin the original page
  184.          * unless an error occurs.
  185.          */
  186.         if (e->index < NEXTINDEX(h))
  187.             break;
  188.         for (;;) {
  189.             if ((pg = h->nextpg) == P_INVALID)
  190.                 goto done1;
  191.             if (h->pgno != save.page->pgno)
  192.                 mpool_put(t->bt_mp, h, dirty2);
  193.             if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) {
  194.                 mpool_put(t->bt_mp, save.page, dirty1);
  195.                 return (RET_ERROR);
  196.             }
  197.             if (NEXTINDEX(h) != 0) {
  198.                 e->page = h;
  199.                 e->index = 0;
  200.                 break;
  201.             }
  202.         }
  203.  
  204.         if (__bt_cmp(t, key, e) != 0)
  205.             break;
  206.     }
  207.  
  208.     /*
  209.      * Reach here with the original page and the last page referenced
  210.      * pinned (they may be the same).  Release it if not the original.
  211.      */
  212. done1:    if (h->pgno != save.page->pgno)
  213.         mpool_put(t->bt_mp, h, dirty2);
  214.  
  215.     /*
  216.      * Walk backwards from the record previous to the record returned by
  217.      * __bt_search, skipping empty pages, until a record doesn't match
  218.      * the key or reach the beginning of the tree.
  219.      */
  220.     *e = save;
  221.     for (;;) {
  222.         if (e->index)
  223.             --e->index;
  224.         for (h = e->page; e->index; --e->index) {
  225.             if (__bt_cmp(t, key, e) != 0)
  226.                 goto done2;
  227.             if (h->pgno == cpgno && e->index == cindex) {
  228.                 if (!ISSET(t, B_DELCRSR)) {
  229.                     SET(t, B_DELCRSR);
  230.                     deleted = 1;
  231.                 }
  232.             } else {
  233.                 if (__bt_dleaf(t, h, e->index) == RET_ERROR) {
  234.                     mpool_put(t->bt_mp, h, dirty1);
  235.                     return (RET_ERROR);
  236.                 }
  237.                 if (h->pgno == save.page->pgno)
  238.                     dirty1 = MPOOL_DIRTY;
  239.                 deleted = 1;
  240.             }
  241.         }
  242.  
  243.         if ((pg = h->prevpg) == P_INVALID)
  244.             goto done2;
  245.         mpool_put(t->bt_mp, h, dirty1);
  246.         dirty1 = 0;
  247.         if ((e->page = mpool_get(t->bt_mp, pg, 0)) == NULL)
  248.             return (RET_ERROR);
  249.         e->index = NEXTINDEX(e->page);
  250.     }
  251.  
  252.     /*
  253.      * Reach here with the last page that was looked at pinned.  Release
  254.      * it.
  255.      */
  256. done2:    mpool_put(t->bt_mp, h, dirty1);
  257.     return (deleted ? RET_SUCCESS : RET_SPECIAL);
  258. }
  259.  
  260. /*
  261.  * __BT_DLEAF -- Delete a single record from a leaf page.
  262.  *
  263.  * Parameters:
  264.  *    t:    tree
  265.  *    index:    index on current page to delete
  266.  *
  267.  * Returns:
  268.  *    RET_SUCCESS, RET_ERROR.
  269.  */
  270. int
  271. __bt_dleaf(t, h, index)
  272.     BTREE *t;
  273.     PAGE *h;
  274.     int index;
  275. {
  276.     register BLEAF *bl;
  277.     register indx_t *ip, offset;
  278.     register size_t nbytes;
  279.     register int cnt;
  280.     char *from;
  281.     void *to;
  282.  
  283.     /*
  284.      * Delete a record from a btree leaf page.  Internal records are never
  285.      * deleted from internal pages, regardless of the records that caused
  286.      * them to be added being deleted.  Pages made empty by deletion are
  287.      * not reclaimed.  They are, however, made available for reuse.
  288.      *
  289.      * Pack the remaining entries at the end of the page, shift the indices
  290.      * down, overwriting the deleted record and its index.  If the record
  291.      * uses overflow pages, make them available for reuse.
  292.      */
  293.     to = bl = GETBLEAF(h, index);
  294.     if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR)
  295.         return (RET_ERROR);
  296.     if (bl->flags & P_BIGDATA &&
  297.         __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR)
  298.         return (RET_ERROR);
  299.     nbytes = NBLEAF(bl);
  300.  
  301.     /*
  302.      * Compress the key/data pairs.  Compress and adjust the [BR]LEAF
  303.      * offsets.  Reset the headers.
  304.      */
  305.     from = (char *)h + h->upper;
  306.     memmove(from + nbytes, from, (char *)to - from);
  307.     h->upper += nbytes;
  308.  
  309.     offset = h->linp[index];
  310.     for (cnt = index, ip = &h->linp[0]; cnt--; ++ip)
  311.         if (ip[0] < offset)
  312.             ip[0] += nbytes;
  313.     for (cnt = NEXTINDEX(h) - index; --cnt; ++ip)
  314.         ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
  315.     h->lower -= sizeof(indx_t);
  316.     return (RET_SUCCESS);
  317. }
  318.